/*
 * @lc app=leetcode.cn id=51 lang=swift
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var res: [[String]] = []
        func valid(_ chess: [[String]], _ row: Int, _ col: Int) -> Bool {
            // 当前列
            for i in 0..<chess.count {
                if chess[i][col] == "Q" {
                    return false
                }
            }
            // 左上角
            var j = col - 1
            for i in stride(from: row-1, through: 0, by: -1) {
                if j >= 0 {
                    if chess[i][j] == "Q" {
                        return false
                    }
                    j -= 1
                }
            }

            // 右上角
            j = col + 1
            for i in stride(from: row-1, through: 0, by: -1) {
                if j < chess.count {
                    if chess[i][j] == "Q" {
                        return false
                    }
                    j += 1
                }
            }

            return true
        }

        func dns(_ chess: [[String]], _ row: Int) {
            if row == chess.count {
                res.append(chess.map { $0.joined(separator: "") })
                return
            }
            for col in 0..<chess.count {
                if !valid(chess, row, col) {
                    continue
                }
                var newChess = chess
                newChess[row][col] = "Q"
                dns(newChess, row+1)
            }
        }

        dns(Array(repeating: Array(repeating: ".", count: n), count: n), 0)
        return res
    }
}
// @lc code=end

